package com.fang.algorithm.zuo.tree;

import java.util.Stack;

/**
 * @author lingxiao.fang
 * @Desc 二叉树的左中右序遍历 栈
 * @createTime 2025/2/26 10:24
 */
public class Test02_LeftRightMidTree_Stack {
    private static class NodeTree {
        private Integer value;
        private NodeTree left;
        private NodeTree right;

        public NodeTree(Integer value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        NodeTree head = new NodeTree(1);
        head.left = new NodeTree(2);
        head.right = new NodeTree(3);
        head.left.left = new NodeTree(4);
        head.left.right = new NodeTree(5);
        head.right.left = new NodeTree(6);
        head.right.right = new NodeTree(7);
        // 前序
//        pre(head);
        // 中序
        mid(head);
        // 后序
//        after(head);
    }

    private static void pre(NodeTree head) {
        if (head == null) {
            return;
        }
        // 先push+pop头节点，再push右节点，再push左节点，pop（形成了头、左、右）
        Stack<NodeTree> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.println(head.value);
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }

    private static void mid(NodeTree head) {
        if (head == null) {
            return;
        }
        Stack<NodeTree> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.println(head.value);
                stack.push(head.right);
            }
        }
    }

    private static void after(NodeTree head) {
        if (head == null) {
            return;
        }
        // 后序遍历和前序类似
        // 先push+pop头节点，再push左节点，再push右节点，pop（形成了头、右、左），再倒过来输出实现
        Stack<NodeTree> stack = new Stack<>();
        Stack<NodeTree> printStack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            printStack.push(head);
            if (head.left != null) {
                stack.push(head.left);
            }
            if (head.right != null) {
                stack.push(head.right);
            }
        }
        while (!printStack.isEmpty()) {
            System.out.println(printStack.pop().value);
        }
    }
}
